\documentclass[submission]{FPSAC2017}

\articlenumber{19}
\addbibresource{19_Bouvel_Guerrini_Rechnitzer_Rinaldi.bib}


\usepackage{amsfonts,xspace,float}
\usepackage{mathtools}

\newcommand{\commonpat}{2\underbracket[.5pt][1pt]{41}3}
\newcommand{\baxpat}{3\underbracket[.5pt][1pt]{14}2}
\newcommand{\twistedpat}{3\underbracket[.5pt][1pt]{41}2}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}

\renewcommand{\qedsymbol}{\normalsize $\Box$}


\title{Semi-Baxter and strong-Baxter permutations}

\author{Mathilde Bouvel\addressmark{1}, Veronica Guerrini\thanks{Corresponding author (\href{mail:guerrini55@student.unisi.it}{guerrini55@student.unisi.it}).}\addressmark{2}, 
Andrew Rechnitzer\addressmark{3} \and Simone Rinaldi\addressmark{2}}

\address{\addressmark{1}Institut f\"ur Mathematik, Universit\"at Z\"urich, Zurich, Switzerland \\ 
\addressmark{2}Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Universit\`a di Siena, Siena, Italy \\ 
\addressmark{3}Mathematics Department, University of British Columbia, Vancouver, BC, Canada\vspace{2pt}}

\received{November 10, 2016}

\revised{March 1st, 2017}

\abstract{In this paper, we enumerate two families of pattern-avoiding permutations: 
those avoiding the vincular pattern $2\underbracket[.5pt][1pt]{41}3$, which we call semi-Baxter permutations, 
and those avoiding the vincular patterns $2\underbracket[.5pt][1pt]{41}3$, $3\underbracket[.5pt][1pt]{14}2$ and $3\underbracket[.5pt][1pt]{41}2$, which we call strong-Baxter permutations. 
For each of these families, we describe a generating tree, which translates into a functional equation for the generating function. 
For semi-Baxter permutations, it is solved using (a variant of) the kernel method, giving an expression for the generating function and both a closed and a recursive formula for its coefficients. 
For strong-Baxter permutations, we show that their generating function is (a slight modification of) that of a family of walks in the quarter plane, 
which is known to be non D-finite.}

\resume{Dans cet article, nous \'enum\'erons deux familles de permutations \`a motifs exclus: 
celles \'evitant le motif vinculaire $2\underbracket[.5pt][1pt]{41}3$, que nous appelons permutations semi-Baxter, 
et celles \'evitant les motifs vinculaires $2\underbracket[.5pt][1pt]{41}3$, $3\underbracket[.5pt][1pt]{14}2$ et $3\underbracket[.5pt][1pt]{41}2$, que nous appelons permutations fortement Baxter. 
Pour chacune de ces familles, nous d\'ecrivons un arbre de g\'en\'eration, qui se traduit en une \'equation fonctionnelle sur la s\'erie g\'en\'eratrice. 
Pour les permutations semi-Baxter, cette \'equation est r\'esolue en utilisant (une variante de) la m\'ethode du noyau, 
donnant une expression de la s\'erie g\'en\'eratrice, ainsi qu'une formule close et une r\'ecurrence pour ses coefficients. 
Pour les permutations fortement Baxter, nous montrons que leur s\'erie g\'en\'eratrice est (une l\'eg\`ere variante de) celle d'une famille de chemins dans le quart de plan, 
qui n'est pas diff\'erentiellement finie.} 

\keywords{Pattern-avoiding permutations; generating trees; generating functions; Baxter numbers.}


\begin{document}

\maketitle

\section{Introduction}

Pattern-avoiding permutations have been the subject of many articles in enumerative combinatorics. 
Here, we are specifically interested in the enumeration of two families of pattern-avoiding permutations, closely related to Baxter and twisted Baxter permutations. 
Recall that a permutation $\pi = \pi_1 \pi_2 \ldots \pi_n$ contains the vincular pattern $\commonpat$ (respectively $\baxpat$, respectively $\twistedpat$) 
if there exists a subsequence $\pi_i \pi_j \pi_{j+1} \pi_k$ of $\pi$ (with $i<j<k-1$) 
that satisfies $\pi_{j+1} < \pi_i < \pi_k < \pi_j$ (respectively $\pi_{j} < \pi_k < \pi_i < \pi_{j+1}$, respectively $\pi_{j+1} < \pi_k < \pi_i < \pi_j$). 
A permutation not containing a pattern avoids it. 
Baxter permutations~\cite[among many others]{BM} are those that avoid both $\commonpat$ and $\baxpat$, 
while twisted Baxter permutations~\cite[and references therein]{Twis} are the ones avoiding $\commonpat$ and $\twistedpat$. 
Both these families are enumerated by Baxter numbers~\cite[sequence A001181]{OEIS}. 

We will first be interested in permutations avoiding the pattern $\commonpat$, 
the pattern whose avoidance is required both in Baxter and twisted Baxter permutations. 
We propose to call such permutations \emph{semi-Baxter permutations}. 
Their enumeration sequence is A117106 in~\cite{OEIS}. 
Note that permutations counted by A117106 are defined as those avoiding the barred pattern $21\bar{3}54$. 
But they are shown in~\cite{Pudwell} to be equinumerous with those avoiding $25\bar{3}14$, whose avoidance is clearly equivalent to that of $\commonpat$. 
The first few terms ($1,2,6,23,104,530,2958, \ldots$) of the sequence A117106 have been originally obtained using enumeration schemes~\cite{Pudwell}. 
We solve completely the problem of enumerating semi-Baxter permutations, pushing further the techniques that were used to enumerate Baxter permutations in~\cite{BM}. 
We provide a generating tree with two labels for semi-Baxter permutations, by means of a succession rule. 
For references on generating trees and succession rules, see for example~\cite{GFGT,Eco,BM}. 
Then, we solve the functional equation associated with it using variants of the kernel method \cite{BM,iteratedKM}. 
This results in an expression for the generating function for semi-Baxter permutations. 
From it, the Lagrange inversion formula gives an explicit but complicated closed formula for the semi-Baxter coefficients. 
However, we show that these coefficients satisfy a simple recurrence formula, which follows from the previous formula applying the method of \emph{creative telescoping}~\cite{zeilberger}. 
As a consequence, our result also answers the question of Bousquet-M\'elou and Butler in~\cite{BB} regarding the enumeration of $21\bar{3}54$-avoiding permutations.

The second family of permutations that we study consists of those that are both Baxter and twisted Baxter permutations, 
that is to say avoid all three patterns $\commonpat$, $\baxpat$ and $\twistedpat$. 
We call these {\em strong-Baxter permutations}. 
Again, we provide a generating tree for them, and translate the corresponding succession rule into a functional equation for their generating function. 
However, we do not solve the equation using the kernel method. 
Instead, from the functional equation, we prove that the generating function for strong-Baxter permutations is a very close relative 
of the one for a family of walks in the quarter plane studied in~\cite{bostan}.
As a consequence, the generating function for strong-Baxter permutations is not D-finite. 
Families of permutations with non D-finite generating functions are quite rare in the literature on pattern-avoiding permutations 
(although mostly studied for classical patterns, instead of vincular ones): this makes the example of strong-Baxter permutations particularly interesting.

\section{Semi-Baxter permutations}

\subsection{Generating tree}

Throughout the paper we will build permutations of increasing sizes by performing ``local expansions'' on the right of any permutation $\pi$. 
More precisely, when inserting $a \in \{1, \ldots, n+1\}$ on the right of any $\pi$ of size $n$, 
we obtain the permutation $\pi' = \pi'_1 \ldots \pi'_{n}\pi'_{n+1}$ where $\pi'_{n+1}=a$, $\pi'_i = \pi_i$ if $\pi_i < a$ and $\pi'_i = \pi_i +1$ if $\pi_i \geq a$. 
We use the notation $\pi \cdot a$ to denote $\pi'$. 
For instance, $1\,4\,2\,3 \cdot 3 = 1\,5\,2\,4\,3$.
This is easily understood on the diagrams representing permutations (which consist of points in the Cartesian plane at coordinates $(i,\pi_i)$): 
a local expansion corresponds to adding a new point on the right of the diagram, which lies vertically between two existing points (or below the lowest, or above the highest), 
and finally normalizing the picture obtained -- see \cref{fig:semi,fig:strong}. 

\begin{proposition}
\label{prop:semi_rule}
Semi-Baxter permutations can be generated by the following succession rule: 
$$\Omega_{semi}=\left\{\begin{array}{ll}
(1,1)\\
(h,k) \rightsquigarrow \hspace{-3mm}& (1,k+1), \ldots , (h,k+1)\\
& (h+k,1), \ldots , (h+1,k). \end{array}\right.$$
\end{proposition}

\begin{figure}[ht]
\centering
\includegraphics[width=0.8\textwidth]{2413av_growth_blu}
\caption{The growth of semi-Baxter permutations. Active sites are marked with $\Diamond$, non-active sites by $\times$, and non-empty descents are represented with bold blue lines.}
\label{fig:semi}
\end{figure}


\begin{proof} 
First, observe that removing the last element of a permutation avoiding $\commonpat$, we obtain a permutation that still avoids $\commonpat$. 
So, a generating tree for semi-Baxter permutations can be obtained with the local expansions on the right described above. 

For $\pi$ a semi-Baxter permutation of size $n$, the \emph{active sites} are by definition 
the points $a$ (or equivalently the values $a$) such that $\pi \cdot a$ is also semi-Baxter, \emph{i.e.}, avoids $\commonpat$. 
The other points $a$ are called non-active sites. 
An occurrence of $2\underbracket[.5pt][1pt]{31}$ in $\pi$ is a subsequence $\pi_j \pi_i \pi_{i+1}$ (with $j<i$) such that $\pi_{i+1}<\pi_j<\pi_i$. 
Obviously, the non-active sites $a$ of $\pi$ are characterized by the fact that $a \in (\pi_j,\pi_i]$ for some occurrence $\pi_j \pi_i \pi_{i+1}$ of $2\underbracket[.5pt][1pt]{31}$. 
We call a \emph{non-empty descent} of $\pi$ a pair $\pi_i \pi_{i+1}$ such that there exists $\pi_j$ that makes $\pi_j \pi_i \pi_{i+1}$ an occurrence of $2\underbracket[.5pt][1pt]{31}$. 
Note that in the case where $\pi_{n-1} \pi_n$ is a non-empty descent, choosing $\pi_j = \pi_{n} +1$ always gives an occurrence of $2\underbracket[.5pt][1pt]{31}$, 
and it is the smallest possible value of $\pi_j$ for which $\pi_j \pi_{n-1} \pi_n$ is an occurrence of $2\underbracket[.5pt][1pt]{31}$. 

To each semi-Baxter permutation $\pi$ of size $n$, we assign a label $(h,k)$, 
where $h$ (respectively $k$) is the number of the active sites of $\pi$ smaller than or equal to (respectively greater than) $\pi_n$. 
Remark that $h,k\geq1$, since $\pi_n$ and $\pi_n+1$ are always active sites. 
Moreover, the label of the permutation $\pi=1$ is $(1,1)$, which is the root in $\Omega_{semi}$.

Consider a semi-Baxter permutation $\pi$ of size $n$ and label $(h,k)$. 
Proving \cref{prop:semi_rule} amounts to showing that permutations $\pi \cdot a$ have labels $(1,k+1), \ldots , (h,k+1), (h+k,1), \ldots , (h+1,k)$ 
when $a$ runs over all active sites of $\pi$. 
\cref{fig:semi}, which shows an example of semi-Baxter permutation with label $(2,2)$ and all the corresponding $\pi \cdot a$ with their labels, 
should help understanding the case analysis that follows. 
Let $a$ be an active site of $\pi$. 

Assume first that $a > \pi_n$ (this happens exactly $k$ times), so that $\pi \cdot a$ ends with an ascent. 
The occurrences of $2\underbracket[.5pt][1pt]{31}$ in $\pi \cdot a$ are the same as in $\pi$. 
Consequently, the active sites are not modified, except that the active site $a$ of $\pi$ is now split into two active sites of $\pi \cdot a$: 
one immediately below $a$ and one immediately above. 
It follows that $\pi \cdot a$ has label $(h+k+1-i,i)$, if $a$ is the $i$-th active site from the top. 
Since $i$ ranges from $1$ to $k$, this gives the second row of the production of $\Omega_{semi}$. 

Assume next that $a=\pi_n$. Then, $\pi \cdot a$ ends with a descent, but an empty one. 
Similar to the above case, we therefore get one more active site in $\pi \cdot a$ than in $\pi$, 
and $\pi \cdot a$ has label $(h,k+1)$, the last label in the first row of the production of $\Omega_{semi}$. 

Finally, assume that $a < \pi_n$ (this happens exactly $h-1$ times). 
Now, $\pi \cdot a$ ends with a non-empty descent, which is $(\pi_n +1) a$. 
It follows from the discussion at the beginning of this proof that all sites of $\pi \cdot a$ in $(a+1,\pi_n+1]$ become non-active, 
while all others remain active if they were so in $\pi$ (again, with $a$ replaced by two active sites surrounding it, one below it and one above). 
If $a$ is the $i$-th active site from the bottom, it follows that $\pi \cdot a$ has label $(i,k+1)$, hence giving all missing labels in the first row of the production of $\Omega_{semi}$. 
\end{proof}

\begin{remark}
\label{remark:semi_generalizes_Baxter}
It is not hard to see that the succession rule $\Omega_{semi}$ generalizes both the succession rules for Baxter permutations given in~\cite{BM} 
and for twisted Baxter permutations given in~\cite{Twis} (or rather the rule obtained from~\cite{Twis} after changing each label $(q,r)$ into $(r+1,q-1)$). 
\end{remark}


\subsection{Functional equation and generating function}
\label{sec:EqnSemiBax}

For $h,k\geq 1$, let $S_{h,k}(x)\equiv S_{h,k}$ denote the size generating function for semi-Baxter permutations having label $(h,k)$, and let $S(x;y,z)\equiv S(y,z)=\sum_{h,k\geq 1} S_{h,k} y^h z^k$. 

\begin{proposition}
The generating function $S(y,z)$ satisfies the following functional equation:
\begin{equation}\label{funeq1} S(y,z)= xyz+\frac{xyz}{1-y} \left( S(1,z) - S(y,z) \right) + \frac{xyz}{z-y} \left( S(y,z) - S(y,y) \right) .\end{equation}
\end{proposition}

\begin{proof}
Starting from the growth of semi-Baxter permutations according to $\Omega_{semi}$ we write:
{\small
\begin{align*}
S(y,z) &= xyz+x\sum_{h,k\geq 1} S_{h,k} \left( (y+y^2+\dots +y^h)z^{k+1}+(y^{h+k}z+y^{h+k-1}z^2+\dots +y^{h+1}z^k) \right) \\
&= xyz+x\sum_{h,k\geq 1} S_{h,k}\left( \frac{1-y^{h}}{1-y} y\, z^{k+1} + \frac{1-\left(\frac{y}{z}\right)^{k}}{1-\frac{y}{z}}y^{h+1} z^{k}\right) \\
          &= xyz+ \frac{xyz}{1-y} \left ( S(1,z) - S(y,z) \right) + \frac{xyz}{z-y} \left ( S(y,z) - S(y,y) \right) \, . \qedhere
\end{align*}
}
\end{proof}

The linear functional equation~\eqref{funeq1} has two catalytic variables, $y$ and $z$ and its solution $S(y,z)$ is not symmetric in $y$ and $z$.
To solve~\eqref{funeq1} it is convenient to set $y=1+a$ and collect all the terms having $S(1+a,z)$ in them, obtaining the {\em kernel form} of the equation:
\begin{equation}
\label{eq1az}
K(a,z) S(1+a,z)= xz(1+a)+\frac{xz(1+a)}{a}  S(1,z) - \frac{xz(1+a)}{z-1-a} S(1+a,1+a)  ,
\end{equation} 
where the kernel function is $K(a,z)=1-\frac{xz(1+a)}{a}- \frac{xz(1+a)}{z-1-a}$. 
For brevity, we refer to the right-hand side of~\eqref{eq1az} as $R(x,a,z,S(1,z),S(1+a,1+a))$.

The kernel function is quadratic in $a$ and $z$. Denoting $Z_{+}(a)$ and $Z_{\_}(a)$ the zeros of $K(a,z)=0$ with respect to $z$, and $Q=\sqrt{a^2-2ax-6a^2x+x^2+2ax^2+a^2x^2-4a^3x}$, we have 
\begin{align*}
Z_{+}(a) & =\frac{1}{2}\frac{a+x+ax-Q}{x(1+a)}=(1+a)+(1+a)^2x+\frac{(1+a)^3(1+2a)}{a}x^2+O(x^3),\\
Z_{\_}(a) & =\frac{1}{2}\frac{a+x+ax+Q}{x(1+a)}=\frac{a}{(1+a)x}-a-(1+a)^2x-\frac{(1+a)^3(1+2a)}{a}x^2+O(x^3). 
\end{align*}

The kernel root $Z_{\_}$ is not a well-defined power series in $x$, whereas the other kernel root $Z_{+}$ is a power 
series in $x$ whose coefficients are Laurent polynomials in $a$. So, setting $z=Z_{+}$, the function 
$S(1+a,z)$ is a convergent power series in $x$ and the right-hand side of~\eqref{eq1az} is equal to zero, \emph{i.e.} 
$R(x,a,Z_{+},S(1,Z_{+}),S(1+a,1+a))=0$. 

At this point we follow the usual kernel method approach (see for instance~\cite{BM}) and attempt to eliminate the term $S(1,Z_+)$ by 
exploiting symmetry transformations that leave the kernel, $K(a,z)$, unchanged. Examining the kernel shows that the 
transformations $$\Phi:(a,z)\rightarrow\left(\frac{z-1-a}{1+a},z\right)\;\;\;\mbox{ and 
}\;\;\;\Psi:(a,z)\rightarrow\left(a,\frac{z+za-1-a}{z-1-a}\right)$$ leave the kernel unchanged and generate a group 
of order $10$.

Among all the elements of this group, consider the following pairs $(f_1(a,z),f_2(a,z))$: 
{\small
$$\left[a,z\right]\mathop{\longleftrightarrow}_{\Phi}\left[\frac{z- 1- a}{1+a},z\right]\mathop{\longleftrightarrow}_{\Psi}\left[\frac{z- 1- a}{1+a},\frac{z-1}{a}\right]\mathop{\longleftrightarrow}_{\Phi}\left[\frac{z- 1- a}{az},\frac{z-1}{a}\right]\mathop{\longleftrightarrow}_{\Psi}
\left[\frac{z- 1- a}{az},\frac{1+a}{a}\right].$$
}
These have been chosen since, for each of them, $f_1(a,Z_{+})$ and $f_2(a,Z_{+})$ are well-defined power series in $x$ with Laurent polynomial coefficients in $a$. 
Moreover, they share the property that $S(1+f_1(a,Z_{+}),f_2(a,Z_{+}))$ are convergent power series in $x$. 
It follows that, substituting each of these pairs for $(a,z)$ in~\eqref{eq1az}, 
we obtain a system of five equations, whose left-hand sides are all $0$, and with six overlapping unknowns. 
Eliminating all unknowns except $S(1+a, 1+a)$ and $S(1,1+\bar{a})$ (with, as usual, $\bar{a}=1/a$), this system reduces (after some work) to the following equation, 
where $P(a,z)=\frac{(-z+1+a)}{z(z-1)a^4}(-za^4+z^2a^4-za^3+z^2a^3-z^3a^2-2a^2+z^2a^2+za^2-4a+5az-3az^2+z^3a+3z-z^2-2)$:
\begin{equation}
\label{final}
S(1+a, 1+a)-\frac{(1+a)^2x}{a^4}S\left(1,1+\bar{a}\right)+P(a,Z_{+})=0.
\end{equation}


The form of \eqref{final} allows us to separate its terms according to the power of $a$: 
\begin{itemize}
 \item $S(1+a,1+a)$ is a power series in $x$ with polynomial coefficient in $a$ whose lowest power of $a$ is $0$, 
 \item $S(1,1+\bar{a})$ is a power series in $x$ with polynomial coefficient in $\bar{a}$ whose highest power of $a$ is 
$0$; consequently, and since $\frac{(1+a)^2x}{a^4} = x(a^{-4}+2a^{-3}+a^{-2})$, we obtain that $\frac{(1+a)^2x}{a^4}S(1,1+\bar{a})$ is a power series 
in $x$ with polynomial coefficients in $a$ whose highest power of $a$ is $-2$.
\end{itemize}
Hence when we expand the series $-P(a,Z_+)$ as a power series in $x$, the non-negative powers of $a$ in the 
coefficients must be equal to those of $S(1+a,1+a)$, while the negative powers of $a$ come from 
$\frac{(1+a)^2x}{a^4}S(1,1+\bar{a})$.

Then, in order to have a better expression for $P(a,z)$, we perform a further substitution setting $z=w+1+a$. 
More precisely, let $W\equiv W(x;a)$ be the power series in $x$ defined by $W=Z_{+}-(1+a)$. We have the following expression for $P(a,Z_{+})$:
\begin{equation}\label{eqP}
\begin{array}{ll}P(a,W+1+a)=&-\,(1+a)^2\,x-\left(\frac{1}{a^5}+\frac{1}{a^4}+2+2a\right)\,x\,W\\
&-\left(-\frac{1}{a^5}-\frac{1}{a^4}+\frac{1}{a^3}-\frac{1}{a^2}-\frac{1}{a}+1\right)\,x\,W^2+\,\left(\frac{1}{a^4}-\frac{1}{a^2}\right)\,x\,W^3.
\end{array}
\end{equation}
Moreover, since $K(a,W+1+a)=0$, the function $W$ is recursively defined by $W=x\,(W+1+a)(1+a)\left(\frac{W}{a}+1\right)$. 

So, this gives an expression for the generating function for semi-Baxter permutations.
\begin{thm}\label{thm:GFSemiBaxter}
Let $W(x;a)\equiv W$ be the unique formal power series in $x$ such that
\begin{equation}
\label{Wexpr}
W=x\bar{a}(1+a)(W+1+a)(W+a).
\end{equation}
The series solution $S(y,z)$ of \eqref{funeq1} satisfies 
$S(1+a,1+a)={\Omega}_{\geq}[-\,P(a,W+1+a)]$, 
where $P(a,W+1+a)$ is defined 
in~\eqref{eqP} and $\mathop{\Omega}_{\geq}[-\,P(a,W+1+a)]$ stands for the formal power series in $x$ obtained by considering 
only those terms in the series expansion that have non-negative powers of $a$.
\end{thm}

\subsection{Semi-Baxter coefficients}

Let $SB_n$ be the coefficient of $x^n$ in $S(1,1)$, which is the number of semi-Baxter permutations of size $n$. 
We can use Lagrange inversion to obtain a closed formula for $SB_n$. Note that this number is also the 
coefficient $[a^0x^n]S(1+a,1+a)$, and so by the above theorem it is the coefficient of $a^0x^n$ in $-\,P(a,W+1+a)$, 
namely 
$SB_n=[a^0x^{n-1}] \Big((1+a)^2+$ $\left(\frac{1}{a^5}+\frac{1}{a^4}+2+2a\right)\,
W+\left(-\frac{1}{a^5}-\frac{1}{a^4}+\frac{1}{a^3}-\frac{1}{a^2}-\frac{1}{a}+1\right)\,W^2+\left(\frac{1}{a^4}-\frac{1}{a^2}\right)\,W^3\Big)$. 
This expression can be evaluated from $[a^sx^k]W^i$, for $i=1,2,3$. Precisely,
{\small
\begin{align*}
SB_n = & [a^5x^{n-1}]W+[a^4x^{n-1}]W+2[a^0x^{n-1}]W+2[a^{-1}x^{n-1}]W-[a^5x^{n-1}]W^2-[a^4x^{n-1}]W^2\\
& +[a^3x^{n-1}]W^2-[a^2x^{n-1}]W^2-[ax^{n-1}]W^2+[a^0x^{n-1}]W^2+[a^4x^{n-1}]W^3-[a^2x^{n-1}]W^3.
\end{align*}
}
Lagrange inversion and the formula~\eqref{Wexpr} then prove that, for $i=1,2,3$, 
$[a^sx^k]W^i=\frac{i}{k}\sum_{j=0}^{k-i}\binom{k}{j}\binom{k}{j+i}\binom{k+j+i}{j+s}$. 
We can then substitute this into the above expression and so, for $n\geq2$, express $SB_n$ as $SB_n=\sum_{j=0}^{n-1} F_{SB}(n,j)$, where
\begin{equation*}
\begin{array}{lll}
F_{SB}(n,j)&=&\frac{1}{n-1}\binom{n-1}{j}\left\{\binom{n-1}{j+1}\left[\binom{n+j+1}{j+5}+2\binom{n+j+1}{j}\right]+2\binom{n-1}{j+2}\left[-\binom{n+j+2}{j+5}+\binom{n+j+1}{j+3}\right.\right.\\
&&\left.-\binom{n+j+2}{j+2}+\binom{n+j+1}{j}\right]\left.+3\binom{n-1}{j+3}\left[\binom{n+j+2}{j+4}-\binom{n+j+2}{j+2}\right]\right\}.
\end{array}
\end{equation*}
Then, manipulating the products in each term by means of binomial coefficient identities we obtain an explicit formula for the semi-Baxter coefficients.
\begin{corollary}\label{cor:CoefSemiBaxter}
The number $SB_n$ of semi-Baxter permutations of size $n$ satisfies:
\begin{equation*}\begin{array}{ll}
\textrm{for all } n\geq1,\ SB_{n+1}=&\frac{1}{n}\sum_{j=0}^{n}\binom{n}{j}\left[2\,\binom{n+1}{j+2}\binom{n+j+2}{n+2}+\binom{n}{j+1}\binom{n+j+2}{n-3}+3\,\binom{n}{j+4}\binom{n+j+4}{n+1}\right.\\
&\left.+2\binom{n}{j+2}\binom{n+j+4}{n}(2-\frac{n+j+5}{n+1}-\frac{n}{j+5})+\frac{2n}{j+3}\,\binom{n}{j+2}\binom{n+j+2}{n}\right].\end{array}
\end{equation*}
\end{corollary}

Surprisingly the above complicated expression hides a very simple recurrence, 
which is not unlike a known recurrence for Baxter numbers.
\begin{proposition}\label{prop:recSemiBaxter}
The numbers $SB_n$ are recursively defined by $SB_0=0$, $SB_1=1$ and for $n\geq2$
\begin{equation*}SB_n=\frac{11n^2+11n-6}{(n+4)(n+3)}SB_{n-1}+\frac{(n-3)(n-2)}{(n+4)(n+3)}SB_{n-2}.\end{equation*}
\end{proposition}

\begin{proof}
In the expression $SB_n=\sum_{j=0}^{n-1} F_{SB}(n,j)$, since the summand $F_{SB}(n,j)$ is hypergeometric, we can prove the recurrence using \emph{creative telescoping}~\cite{zeilberger}. 
The Maple package {\tt ZEILBERGER} implements this approach and yields a certificate proving our claim.
\end{proof}

From this recurrence we can recover the dominant asymptotics of the coefficients by a straightforward application 
of the methods described in~\cite{wimp}.
\begin{corollary}
$SB_n\mathop{\sim}\limits_{n\rightarrow\infty} A\,\frac{\mu^{n}}{n^{6}}\left(1+O\left(\frac{1}{n}\right)\right)$, 
where $\mu=\frac{11}{2}+\frac{5}{2}\sqrt{5}$ and $A \approx 94.34$ is a constant.
\end{corollary}

\section{Strong-Baxter permutations}

Recall that the family of strong-Baxter permutations is defined by the avoidance of $\commonpat$, $\baxpat$ and $\twistedpat$, 
that it to say it is the intersection of the families of Baxter and twisted Baxter permutations. 

\subsection{Generating tree}

\begin{proposition} Strong-Baxter permutations can be generated by the following succession rule: 
$$\Omega_{strong}=\left\{\begin{array}{ll}
(1,1)\\
(h,k) \rightsquigarrow \hspace{-3mm}& (1,k), \ldots ,(h-1,k), (h,k+1)\\
& (h+1,1), \ldots , (h+1,k). \end{array}\right.$$
\end{proposition}

\begin{figure}[ht]
\centering
\includegraphics[width=0.8\textwidth]{strong_growth_blu}
\caption{The growth of strong-Baxter permutations (with notation as in \cref{fig:semi}).}
\label{fig:strong}
\end{figure}

\begin{proof}
As in the proof of \cref{prop:semi_rule}, we build a generating tree for strong-Baxter permutations 
performing local expansions on the right, as illustrated in \cref{fig:strong}. 
Note that this is possible since removing the last point from any strong-Baxter permutation gives a strong-Baxter permutation. 

Let $\pi$ be a strong-Baxter permutation of size $n$. 
By definition, the active sites of $\pi$ are the $a$'s such that $\pi \cdot a$ is a strong-Baxter permutations. 
The label given to $\pi$ is $(h,k)$, where $h$ (respectively $k$) is the number of active sites that are smaller than or equal to (respectively greater than) $\pi_n$. 
As in the proof of \cref{prop:semi_rule}, the permutation $1$ has label $(1,1)$, 
and we now need to describe the labels of the permutations $\pi \cdot a$ when $a$ runs over all active sites of $\pi$. 
So, let $a$ be such an active site. 

If $a < \pi_n$, then $\pi \cdot a$ ends with a non-empty descent. 
As in the proof of \cref{prop:semi_rule}, all sites of $\pi \cdot a$ in $(a+1,\pi_n+1]$ become non-active 
(due to the avoidance of $\commonpat$). 
Moreover, due to the avoidance of $\twistedpat$, the site immediately above $a$ in $\pi \cdot a$ also become non-active. 
All other active sites of $\pi$ remain active in $\pi \cdot a$, hence giving the labels $(i,k)$ for $1 \leq i < h$ in the production of $\Omega_{strong}$
(again, $i$ is such that $a$ is the $i$-th active site from the bottom). 

If $a=\pi_n$, no site of $\pi$ becomes non-active, giving the label $(h,k+1)$ in the production of $\Omega_{strong}$. 

Finally, if $a > \pi_n$, then $\pi \cdot a$ ends with an ascent. 
Because of the avoidance of $\baxpat$, 
we need to consider the occurrences of $2\underbracket[.5pt][1pt]{13}$ in $\pi$ to identify which active sites of $\pi$ become non-active in $\pi \cdot a$. 
It follows from a discussion similar to that in the proof of \cref{prop:semi_rule} 
that all sites of $\pi \cdot a$ in $[\pi_n+1,a)$ become non-active. 
Hence, we obtain the missing labels in the production of $\Omega_{strong}$: 
$(h+1,i)$ for $1 \leq i \leq k$ (where $i$ indicates that $a$ is the $i$-th active site from the top). 
\end{proof}

We have added the sequence enumerating strong-Baxter permutations to the OEIS, where it is now registered as \cite[A281784]{OEIS}. It starts with:
$1,2,6,21,82,346,1547, \ldots$.

\begin{remark}
Similarly to \cref{remark:semi_generalizes_Baxter}, it is easy to see that the succession rule $\Omega_{strong}$ is a specialization 
of the rule $\Omega_{Bax}$ given in~\cite{BM} for Baxter permutations, 
as well as of the rule $\Omega_{TBax}$ (modified as in \cref{remark:semi_generalizes_Baxter}) given in~\cite{Twis} for twisted Baxter permutations. 
In this case, the rule $\Omega_{strong}$ associated with the intersection of these two families is simply obtained by taking, for each object produced, 
the minimum label among the two labels given by $\Omega_{Bax}$ and $\Omega_{TBax}$.
This appears clearly in the following representation:
$$\begin{array}{lllcccccccc}
\Omega_{Bax}:&(h,k)&\rightarrow&(1,k+1)&\ldots&(h-1,k+1)&(h,k+1)&(h+1,1)&\ldots&(h+1,k)\\ 
\Omega_{TBax}:&(h,k)&\rightarrow&(1,k)&\ldots&(h-1,k)&(h,k+1)&(h+k,1)&\ldots&(h+1,k)\\ 
\Omega_{strong}:&(h,k)&\rightarrow&(1,k)&\ldots&(h-1,k)&(h,k+1)&(h+1,1)&\ldots&(h+1,k).
\end{array}$$ 
\end{remark}

\subsection{Functional equation and generating function}

Let $I_{h,k}(x)\equiv I_{h,k}$ denote the generating function for strong-Baxter permutations having label $(h,k)$, with $h,k\geq1$, and let $I(x;y,z)\equiv I(y,z)=\sum_{h,k\geq 1} I_{h,k} y^h z^k$. 
(The notation $I$ stands for Intersection, of the families of Baxter and twisted Baxter permutations.)

\begin{proposition}
The generating function $I(y,z)$ satisfies the following functional equation:
\begin{equation}
\label{inters} 
I(y,z)=xyz+\frac{x}{1-y}(y\,I(1,z)-I(y,z))+xz\,I(y,z)+\frac{xyz}{1-z}(I(y,1)-I(y,z)).
\end{equation}
\end{proposition}

\begin{proof} 
From the growth of strong-Baxter permutations according to $\Omega_{strong}$ we write:
{\small
\begin{align*}
I(y,z) &= xyz+x\sum_{h,k\geq 1} I_{h,k} \left( (y+y^2+\dots +y^{h-1})z^{k}+y^h z^{k+1}+y^{h+1}(z+z^2+\dots +z^k) \right) \\
&= xyz+x\sum_{h,k\geq 1} I_{h,k}\left( \frac{1-y^{h-1}}{1-y} y\, z^{k} +y^h z^{k+1}+  \frac{1-z^{k}}{1-z} y^{h+1}\, z\right) \\
          &= xyz+ \frac{x}{1-y} \left (y\,I(1,z) - I(y,z) \right) + xz\,I(y,z)+\frac{xyz}{1-z} \left ( I(y,1) - I(y,z) \right) \, . \qedhere
\end{align*}
}
\end{proof}

Our goal for the end of this section is to prove the following:

\begin{thm}
\label{naturegf}
The generating function $I(1,1)$ for strong-Baxter permutations is not D-finite.
\end{thm}

In order to study the nature of the generating function $I(1,1)$ we look at the kernel of Equation \eqref{inters}, which is
\begin{equation}
\label{kernel_in}
K(y,z)=1+x\left(\frac{1}{1-y}-z+\frac{yz}{1-z}\right).
\end{equation}
We perform the substitutions $y=1+a$ and $z=1+b$ so that \eqref{kernel_in} becomes 
\begin{equation}
\label{kerab_in}
K(1+a,1+b)= 1-x Q(a,b) \textrm{ \ where \ } Q(a,b) = \frac{1}{a}+\frac{1}{b}+\frac{a}{b}+a+2+b.
\end{equation}

The kernel $K(1+a,1+b)$ is not symmetric in $a$ and $b$. As in \cref{sec:EqnSemiBax}, we look for the birational transformations 
$\Phi$ and $\Psi$ in $a$ and $b$ that leave the kernel unchanged, which are: 
$$\Phi:(a,b)\rightarrow\left(a,\frac{1+a}{b}\right),\;\;\;\mbox{ and 
}\;\;\;\Psi:(a,b)\rightarrow\left(-\frac{b}{a(1+b)},b\right).$$
One observes, using Maple for example, that the group generated by these two transformations is not of small order. 
We actually suspect that it is of infinite order. 

After the substitution $y=1+a$ and $z=1+b$, the kernel we obtain in \eqref{kerab_in} resembles kernels of functional equations 
associated with the enumeration of families of walks in the quarter plane. 
Making this connection precise will allow us to prove \cref{naturegf}. 

\medskip

Consider walks confined in the quarter plane and using $\{(-1,0)$, $(0,-1),(1,-1)$, $(1,0)$, $(0,1)\}$ as step set. 
Let $W(t;a,b)$ be the generating function for such walks, 
where $t$ counts the number of steps and $a$ (respectively $b$) records the $x$-coordinate (respectively $y$-coordinate) of the ending point. 
With classical arguments for counting walks confined in the quarter plane, we see that the function $W(t;a,b)$ satisfies:
\begin{equation}\label{walks}
W(t;a,b)=1+t\left(\frac{1}{a}+\frac{1}{b}+\frac{a}{b}+a+b\right)W(t;a,b)-\frac{t}{a}W(t;0,b)-t\frac{(1+a)}{b}W(t;a,0).
\end{equation}
It is proved in~\cite{bostan} that the generating functions $W(t;a,b)$ and $W(t;0,0)$ are not D-finite.

\medskip

Note that, writing \eqref{walks} in kernel form, we see the following kernel function appearing: 
$1-t\left(\frac{1}{a}+\frac{1}{b}+\frac{a}{b}+a+b\right) = 1-tQ(a,b)+2t$. 
It is almost identical to the kernel $K(1+a,1+b)=1-tQ(a,b)$ of Equation \eqref{inters} as written in \eqref{kerab_in}.
Indeed, we can even modify the step set so that $K(1+a,1+b)$ is exactly the kernel arising in the functional equation for enumerating a family of walks: 
it is enough to add two trivial steps, hence considering the step (multi-)set 
$\mathfrak{S}=\{(-1,0),(0,-1),(1,-1),(1,0),(0,1),(0,0), (0,0)\}$, 
where the two copies of $(0,0)$ are distinguished (by colors for instance). 

Let us denote $W_2(x;a,b)$ the generating function for such walks, where $x$ counts the number of steps and $(a,b)$ records the coordinates of the ending point. 
Walks counted by $W_2$ can be described from walks counted by $W$ as follows: 
a $W_2$-walk is a (possibly empty) sequence of trivial steps, followed by a $W$-walk where, after each step, we insert a (possibly empty) sequence of trivial steps. 
This simple combinatorial argument shows that $W_2(x;a,b) =W(\frac{x}{1-2x};a,b) \frac{1}{1-2x}$. 
Since $\frac{1}{1-2x}$ and $\frac{x}{1-2x}$ are algebraic series, and neither $W(t;a,b)$ nor $W(t;0,0)$ are D-finite, 
we conclude that, for the step set $\mathfrak{S}$ as well, 
both the full generating function $W_2(x;a,b)$ and the generating function of excursions $W_2(x;0,0)$ are not D-finite.

\begin{proof}[Proof of \cref{naturegf}]
For ease of exposition, let us write $J(x;a,b):=I(x;1+a,1+b)$. 
With this notation, the statement of \cref{naturegf} is that $J(x;0,0)$ is not D-finite. 
To prove this, we relate $J(x;a,b)$ and $W_2(x;a,b)$, and use the non D-finiteness of $W_2(x;0,0)$. 
Namely, we show that $J(x;a,b) = (1+a)(1+b)\,x\,W_2(a,b;x)$.

Consider the kernel form of \eqref{inters} after substituting $y=1+a$ and $z=1+b$, which is 
\begin{equation}\label{comparing1}
(1-xQ(a,b)) J(x;a,b)=x(1+a)(1+b)-x\,\frac{1+a}{a}\,J(x;0,b)-x\,\frac{(1+a)(1+b)}{b}\,J(x;a,0).
\end{equation}
Compare it to the kernel form of \eqref{walks}:
\begin{equation}\label{comparing2}
(1-t(Q(a,b)-2))W(t;a,b)=1-\frac{t}{a}\,W(t;0,b)-t\,\frac{(1+a)}{b}\,W(t;a,0).
\end{equation}

Substituting $t$ with $\frac{x}{1-2x}$ in~\eqref{comparing2}, and multiplying this equation by $(1+a)(1+b)x$, 
we see that $(1+a)(1+b)\,x\,W_2(x;a,b)$ satisfies \eqref{comparing1}, proving our claim. 

Hence, the generating function $I(x;1,1) = J(x;0,0)$ of strong-Baxter permutations and the generating function $W_2(x;0,0)$ of $\mathfrak{S}$-excursions in the quarter plane coincide, up to a factor $x$. 
And \cref{naturegf} follows from the non D-finiteness of $W_2(x;0,0)$. 
\end{proof}

Moreover, some information on the asymptotic behavior of the number of strong-Baxter permutations 
can be derived from the following proposition, as presented in~\cite{bostan}. 

\begin{proposition}[Denisov and Wachtel]\label{DW}
Let $\mathfrak{S}\subseteq\{0,\pm1\}^2$ be a step set which is not confined to a half-plane. 
Let $e_n$ denote the number of $\mathfrak{S}$-excursions of length $n$ confined to the quarter plane $\mathbb{N}^2$ and using only steps in $\mathfrak{S}$.
Then, there exist constants $K$, $\rho$, and $\alpha$ which depend only on $\mathfrak{S}$, such that:
\begin{itemize}
\item if the walk is aperiodic, $e_n\sim K\,\rho^n\,n^\alpha$, 
\item if the walk is periodic (then of period 2), $e_{2n}\sim K\,\rho^{2n}\,(2n)^\alpha,\;\; e_{2n+1}=0$. 
\end{itemize}
\end{proposition}

In \cite{bostan} the growth constant $\rho_W$ associated with $W(t;0,0)$ is approximately calculated to be the 
algebraic number $4.729031538$. Using known results about composition of functions, we can relate the growth 
constant of strong-Baxter coefficients to $\rho_W$. 

\begin{corollary}
\label{cor:growth_strong}
The growth constant for the strong-Baxter coefficients is $\rho_W+2 \approx 6.729031538$.
\end{corollary}

\begin{proof}
Recall that $I(x;1,1)=x\,W_2(x;0,0)=x\,W(\frac{x}{1-2x};0,0)\,\frac{1}{1-2x}$, and that $\frac{1}{\rho_W}$ is the radius of convergence of $W(t;0,0)$. 
The radius of convergence of $g(x)=\frac{x}{1-2x}$ is $\frac{1}{2}$, and $\lim_{{x\to 1/2} \atop {x<1/2}}g(x) = +\infty > \frac{1}{\rho_W}$. 
So, the composition $W(g(x);0,0)$ is supercritical (see \cite[p. 411]{Flaj}), and 
the radius of convergence of $W(\frac{x}{1-2x};0,0)$ is $g^{-1}\left(\frac{1}{\rho_W}\right)=\frac{1}{\rho_W+2}$.
Since $\frac{1}{\rho_W+2}$ is smaller than the radius of convergence $\frac{1}{2}$ of $\frac{1}{1-2x}$, $\frac{1}{\rho_W+2}$ is also the radius of convergence of 
$x\,W(\frac{x}{1-2x};0,0)\,\frac{1}{1-2x} = I(x;1,1,)$, proving \cref{cor:growth_strong}. 
\end{proof}


\begingroup\emergencystretch=1em
\printbibliography 
\endgroup


\end{document}
